// 希尔排序 插入排序的演进改变
// 将原数组拆成固定间隔的局部有序数组，从而使插入排序的过程逐步迈入有序
// 当间隔为1是就演变成标准的插入排序

export function shellSort(nums: number[]): number[] {
    let gap = 1;// 间隔初始化为1
    // 找合适的间隔利用了 Knuth 增量序列，可以不做了解
    while (gap * 3 + 1 < nums.length) {
        gap = gap * 3 + 1;
    }
    // 令gap逐渐退化
    while (gap >= 1) {
        // 以下做间隔为gap的插入排序
        for (let i = gap; i < nums.length; i++) {
            for (let j = i; j >= gap; j -= gap) {
                // 每个j - gap组成的子数组其实就是已经排好序的数组
                if (nums[j] < nums[j - gap]) {
                    [nums[j], nums[j - gap]] = [nums[j - gap], nums[j]];
                }
            }
        }
        // 逐渐缩小间隔
        gap = Math.floor(gap / 3);
    }
    return nums;
}